package dp;

public class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for(int a = 0; a <= amount; a++){
            dp[0][a] = 0;
        }
        for(int c = 0; c <= coins.length; c++){
            dp[c][0] = 1;
        }
        for(int c = 1; c <= coins.length; c++){
            for(int a = 1; a <= amount; a++){
                if(a >= coins[c]){
                    dp[c][a] = dp[c-1][a] + dp[c][a-coins[c-1]];
                }else{
                    dp[c][a] = dp[c-1][a];
                }
            }
        }
        return dp[coins.length][amount];
    }
}
